/*

	Adaptive Huffman encoder/decoder
	--------------------------------

	This is an adaptive Huffman en-/decoding model which updates the tree in
	only-the-fly and works with a maximum of a 256 item-sized alphabet.
	Additionally symbols, occurred recently, have smaller bit sequences than
	older ones.

	The algorithm + some comments are ripped out of "The Data Compression Book"
	by Mark Nelson.

	You can make the class compress a data block itself or just use the public
	member functions to do this work outside the class (untested). Maybe you have to
	adjust the class layout a bit for the 2nd method.

	The output buffers are tidied up by the class itself!


	WWW:      y0da.cjb.net
	E-mail:   LordPE@gmx.net

	You are allowed to use this source code in your own projects if you mention
	my name.

	by yoda

*/

#pragma once

#include <windows.h>
#include "ByteWriter.h"
#include "ByteReader.h"

//
// constants
//
#define ALPHABET_SIZE             258
#define ROOT_NODE                 0
#define MAX_COUNT                 0x8000

#define END_OF_STREAM             256
#define ESCAPE                    257

//
// structures
//
//#include <PshPack1.h> // turn on struct 1-byte-alignment

typedef struct _HT_ITEM
{
	DWORD                    dad;
	DWORD                    child;
	BOOL                     bIsLeaf;
	DWORD                    count;

//	DWORD                    dwSequence;                   // bit signature for the character
//	BYTE                     bySequLen;                    // length of the bit signature
} HT_ITEM, *PHT_ITEM;

//#include <PopPack.h>

//
// HuffTree class
//
class AHuff
{
public:
	AHuff();
	~AHuff();

	void    Init();
	void    Dispose();
	void    UpdateModel( BYTE symbol );
	BOOL    EncodeSymbol( ByteWriter &writer, int symbol );
	int     DecodeSymbol( ByteReader &reader );

	BOOL    EncodeData( IN PBYTE pbyInput, IN DWORD cbInput, OUT PBYTE &pOut, OUT DWORD &dwOut );
	BOOL    DecodeData( IN PBYTE pbyInput, IN DWORD cbInput, IN DWORD cbUncompressed, OUT PBYTE &pOut, OUT DWORD &dwOut );

private:
	short int                m_Leafs[ALPHABET_SIZE+1];          // alphabet + root item
	UINT                     m_NextFreeNode;
	HT_ITEM                  m_Nodes[ (2*ALPHABET_SIZE-1) ];
	PBYTE                    m_pOut; // also handled as validator for m_cbOut
	DWORD                    m_cbOut;

	BOOL    FreeOutBuff();
	void    InitTree();
	void    RebuildTree();
	void    AddNewNode( BYTE symbol );
	void    SwapNodes( UINT i, UINT j );
};

typedef AHuff *PAHuff;
